package com.sicheng.蓝桥.练习题.dp;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/3 14:52
 */
public class 最小权值 {
    /**
     * 最小权值
     * 对于—棵有根二叉树 T ，小蓝定义这棵树中结点的权值 W(T') 如下:
     * 空子树的权值为0。
     * 如果一个结点 v 有左子树 L,右子树R，分别有C(L)和C(R)个结点，则 W(v)=1+2W(L)+3W(R)+(C(L))^2C(R) 树的权值定义为树的根结点的权值。
     * 小蓝想知道，对于一棵有2021个结点的二叉树，树的权值最小可能是多少?
     */

    public static void main(String[] args) {
        int n = 2022;
        // dp[i] 表示有i个结点的最小权
        long[] dp = new long[n];
        Arrays.fill(dp, (long) Integer.MAX_VALUE << 3);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n; i++) {
            // j 表示 i个结点的树有j个左孩子，那么就会有i-1-j个右孩子
            for (int j = 0; j < i; j++) {
                dp[i] = Math.min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - 1 - j] + (long) j * j * (i - 1 - j));
            }
        }
        System.out.println(dp[n - 1]);

    }

}
